package main

import "fmt"

//type ListNode struct {
//	Val  int
//	Next *ListNode
//}

func main() {
	fmt.Println(trainningPlan3(&ListNode{2, &ListNode{4, &ListNode{7, &ListNode{8, nil}}}}, &ListNode{1, &ListNode{3, &ListNode{5, &ListNode{6, nil}}}}))
}

func trainningPlan3(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{1, nil}
	curr := res
	for l1 != nil || l2 != nil {
		if l1 != nil && l2 != nil {
			if l1.Val < l2.Val {
				curr.Next = l1
				curr = l1
				l1 = l1.Next
			} else {
				curr.Next = l2
				curr = l2
				l2 = l2.Next
			}
		} else if l1 != nil {
			curr.Next = l1
			break
		} else {
			curr.Next = l2
			break
		}
	}
	return res.Next
}
